//计算右侧小于当前元素的个数
/*给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。*/
class Solution {
    vector<int> temp_n;
    vector<int> temp_i;
    vector<int> ret;

public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> index(n);
        ret.resize(n);
        temp_i.resize(n);
        temp_n.resize(n);
        for (int i = 0; i < n; i++) {
            index[i] = i;
        }
        dfs(nums, index, 0, n - 1);
       // for (auto& num : nums)
        //    cout << num << " ";
        //cout << endl;
        return ret;
    }
    void dfs(vector<int>& nums, vector<int>& index, int l, int r) {
        if (l >= r)
            return;
        int m = l + (r - l) / 2;
        dfs(nums, index, l, m);
        dfs(nums, index, m + 1, r);
        int cur1 = l, cur2 = m + 1, i = 0;
        while (cur1 <= m && cur2 <= r) {
            if (nums[cur1] > nums[cur2]) {
                temp_n[i] = nums[cur1];
                temp_i[i] = index[cur1];
                ret[index[cur1]] += (r - cur2 + 1);
                i++;
                cur1++;
            } else {
                temp_n[i] = nums[cur2];
                temp_i[i] = index[cur2];
                i++;
                cur2++;
            }
        }
        while (cur1 <= m) {
            temp_n[i] = nums[cur1];
            temp_i[i] = index[cur1];
            i++;
            cur1++;
        }
        while (cur2 <= r) {
            temp_n[i] = nums[cur2];
            temp_i[i] = index[cur2];
            i++;
            cur2++;
        }
        for (int i = l; i <= r; i++) {
            nums[i] = temp_n[i - l];
            index[i] = temp_i[i - l];
        }
    }
};

//493. 翻转对

/*给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。*/
//升序
class Solution {
    vector<int> temp;
    int ret = 0;

public:
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        temp.resize(n);
        vector<long long> temp(nums.begin(), nums.end());
        dfs(temp, 0, n - 1);
        // for (auto& num : nums)
        //     cout << num << " ";
        // cout << endl;
        return ret;
    }
    void dfs(vector<long long>& nums, int l, int r) {
        if (l >= r)
            return;
        int m = l + (r - l) / 2;
        dfs(nums, l, m);
        dfs(nums, m + 1, r);
        int l_nums = l;
        int r_nums = m + 1;
        for (; l_nums <= m; l_nums++) {
            while (r_nums <= r) {
                if (nums[l_nums] > nums[r_nums] * 2) {
                    r_nums++;
                } else {
                    break;
                }
            }
            ret += (r_nums - m - 1);
        }
        int cur1 = l, cur2 = m + 1, i = 0;
        while (cur1 <= m && cur2 <= r)
            temp[i++] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++];
        while (cur1 <= m)
            temp[i++] = nums[cur1++];
        while (cur2 <= r)
            temp[i++] = nums[cur2++];
        for (int j = l; j <= r; j++)
            nums[j] = temp[j - l];
    }
};

//降序
class Solution {
    vector<int> temp;
    int ret = 0;

public:
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        temp.resize(n);
        vector<long long> temp(nums.begin(), nums.end());
        dfs(temp, 0, n - 1);
        for (auto& num : temp)
            cout << num << " ";
        cout << endl;
        return ret;
    }
    void dfs(vector<long long>& nums, int l, int r) {
        if (l >= r)
            return;
        int m = l + (r - l) / 2;
        dfs(nums, l, m);
        dfs(nums, m + 1, r);
        int l_nums = l;
        int r_nums = m + 1;
        for (; l_nums <= m; l_nums++) {
            while (r_nums <= r) {
                if (nums[l_nums] <= nums[r_nums] * 2) {
                    r_nums++;
                } else {
                    break;
                }
            }
            ret += (r - r_nums + 1);
        }
        int cur1 = l, cur2 = m + 1, i = 0;
        while (cur1 <= m && cur2 <= r)
            temp[i++] = nums[cur1] > nums[cur2] ? nums[cur1++] : nums[cur2++];
        while (cur1 <= m)
            temp[i++] = nums[cur1++];
        while (cur2 <= r)
            temp[i++] = nums[cur2++];
        for (int j = l; j <= r; j++)
            nums[j] = temp[j - l];
    }
};